package heap;

import java.util.Arrays;

// 优先队列（堆）
// 每棵子树从根结点开始向下调整
// 左右找最大值跟根结点进行比较

public class TestHeap {
    public int[] array;
    public int usedSize; // 有效数组长度：有效元素个数

    //构造方法进行初始化
    public TestHeap() {
        this.array = new int[10];  // 数组的初始化
        this.usedSize = 0;
    }

    // 初始化数组
    public void initArray(int[]arr) {
        this.array = Arrays.copyOf(arr,arr.length); //将数组中元素拷贝给数组
        this.usedSize = this.array.length;
    }

    // createHeap建堆
    // 大根堆
    // 从最后一棵子树进行调整：每棵子树调整方法一样--找左右子树最大值，然后与根结点比较交换
    // 最后一棵子树的最后一个结点（孩子结点）：数组长度-1； 则最后一棵子树父亲节点：（数组长度-1）/2
    // 如何确定下一颗子树的根结点：当前根结点-1
    // 建堆的时间复杂度是 O(n)  -- 使用等差*等比数列求和进行计算
    public void createHeap() {
        // 注意：从最后一个根节点依次向上的根结点遍历，以使得每棵子树都是大堆形式
        for(int parent = (usedSize-1-1)/2; parent>=0; parent--) {
            shiftUp(parent,usedSize);
            // 为啥每棵子树的结束直接写的是usedSize：子树理论上结束的位置其实都是大于usedSize的
        }
    }

    // 大根堆：实现向下调整
    private void shiftUp(int parent, int len) {
        // child 标记左孩子的位置
        int child = 2*parent+1;  //是从最后一颗子树开始的
        // len = this.usedSize; // 最后的位置

        // 该循环是为了保证左孩子的存在
        while(child<len) {
            // 在右子节点存在条件下判断左右子结点值的大小（注意是值的大小！！
            if(child+1<len && array[child]<array[child+1]) {
                child ++; // 使得下标指向值最大的孩子结点
            }
            // 来到这儿说明两种情况：只有左孩子or左孩子小于右孩子--两种情况都是child结点有最大值
            // 判断最大子结点和父亲节点的大小 -- 进行交换swap
            if(array[child] > array[parent]) {
                // 孩子大就进行交换
                swap(array,child,parent);
                // 注意：在交换后要进行根结点与孩子结点的变换
                parent = child;
                child = 2*parent +1;
            } else {
                // 说明此时的子树已经满足条件 不需要再进行任何变化
                break;
            }
        }
    }

    // 交换swap
    private void swap(int[] arr, int child, int parent) {
        // 交换值
        int tmp = arr[child];
        arr[child] = arr[parent];
        arr[parent] = tmp;
    }



    // 插入元素进行调整：

    // 先在末尾放入元素：
    public void offer(int x) {
        // 判满以及扩容
        if(isFull()) {
            this.array = Arrays.copyOf(array,2*array.length);
            // 此处扩容也可以只是加1，一次就扩容一个
        }
        // 进行尾插
        this.array[usedSize] = x;
        this.usedSize++;
        // 进行调整：
        shiftDown(usedSize-1); // 为什么要减1：因为此时usedSize已经在之前加加了，比此时下标大1
        // 注意是usedSize
    }

    // 判满
    private boolean isFull() {
        return this.usedSize==this.array.length;
    }

    // 进行调整 shiftDown
    private void shiftDown(int child) {
        int parent = (child-1)/2;
        // 调整循环条件：child>0
        while(child>0) {
            // 进行与父亲节点的比较
            if(this.array[child] > this.array[parent]) {
                swap(this.array,child,parent);
                // 交换后进行变换
                child = parent;
                parent = (child-1)/2;
            } else {
                break;
            }
        }
    }




    // 删除元素进行调整：

    // 保存出队的元素：
    public int poll() {
        if(isEmpty()) {
            return -1;
        }
        int old = this.array[0];
        swap(this.array,0,this.usedSize-1);
        this.usedSize--;
        // 进行变换
        shiftUp(0,this.usedSize); // 注意该方法其实是在<usdSize时进行变换，所以不需要-1
        return old;
    }

    // 判空
    private boolean isEmpty() {
        return usedSize==0;
    }


    // 堆排序：
    public void heapSort() {
        int end = this.usedSize-1;
        // 循环变换
        while(end>0) {
            // 进行交换
            swap(this.array,0,end);
            // 先进行大根堆的调整，需要到end，因为比较时本来就不包含边界，所以先不进行—-
            shiftUp(0,end);
            end--;
        }
    }
}
